// 分割回文二
class Solution {
    public:
        int minCut(string s) {
            int n = s.size();
            vector<vector<bool>> dp1(n,vector<bool>(n));
            for(int i = n - 1; i >= 0; i--)
            {
                for(int j = i; j < n; j++)
                {
                    if(s[i] == s[j])
                    {
                        dp1[i][j] = i + 1 < j ? dp1[i + 1][j - 1] : true; 
                    }
                }
            }
            // 最小分隔次数
            vector<int> dp2(n,INT_MAX);
    
            for(int i = 0; i < n; i++)
            {
                if(dp1[0][i])
                {
                    dp2[i] = 0;
                }
                else
                {
                    for(int j = 0; j < i; j++)
                    {
                        if(dp1[j+1][i])
                        {
                            dp2[i] = min(dp2[j] + 1, dp2[i]); 
                        }
                    }
                }
            }
    
            return dp2[n-1];
        }
    };